1. Field of the Invention
The present invention relates to circuits for digital signal processing systems, and, more particularly, detecting the overflow flag of a barrel shift operation.
2. Description of the Related Art
Bit manipulation units (BMUs) are circuits commonly employed in digital signal processors (DSPs), micro-controllers, or other types of processors to scale and format data. Typical instructions executed by a BMU include: (a) arithmetic shift left or right, (b) logical shift right, and (c) normalize. Pseudo-code equations (1) through (4) below represent these operations:
where aD0 and aD1 represent resulting output data written to corresponding destination accumulators, and aS0 and aS1 represent input data stored in corresponding source accumulators. For an arithmetic shift right operation, redundant sign bits are shifted in from the left, while for a logic shift right operation, padding bits (logic xe2x80x9c0xe2x80x9d or logic xe2x80x9cIxe2x80x9d) are shifted in from the left. For an arithmetic shift left operation, padding bits are inserted from the right. For a BMU, an operation for logical shift left is generally not defined since a logical shift left operation generates the same numerical result as an arithmetic shift left operation.
A BMU executes one operation in one clock cycle. In the DSP16000 processor available from Lucent Technologies of Murray Hill, N.J., for example, the source and destination accumulators are 40 bits wide; each accumulator may contain up to 32 bits of data and eight guard bits for overflow, and have a maximum shift amount of 31 bits. FIGS. 1(a), 1(b), and 1(c) illustrate changing bit positions for the three shift operations of equations (1), (2), and (3), respectively, in the exemplary prior art processor. For the normalize operation of equation (4), the BMU shifts the bits of the 40-bit input data an appropriate shift amount (number of bit positions) to represent the value with a 32-bit result and an exponent.
FIG. 2 shows logic circuit 200 for an exemplary implementation of a prior art BMU 201 and external accumulator 202. The circuit 200 has three primary input values: (a) the data aS0, which is a sequence of bit values, (b) the shift value, which is the direction (indicated by the sign bit of the shift value) and number of bit positions by which the data is to be shifted corresponding to the shift amount, and (c) the saturation mode value SAT. The saturation mode value SAT identifies whether the output values are to be limited to a 32-bit sequence. The data aS0 is provided to BMU 201 from, for example, 40-bit wide first source accumulator included in external accumulator 202. The shift value may be the shift value aS1 that is provided to BMU 201 from the upper half of a second source accumulator, that may be included in external accumulator 202, or the shift value may be an immediate value from the instruction itself. The shift value aS1 may be limited to 6 bits by limiter 210. The saturation mode value SAT is provided from an external control register (not shown) that is set by an instruction. If the saturation mode value SAT is enabled, as described subsequently, then a result generated by BMU 201 may be limited to a length of 32 bits. In addition, the input value SHIFT identifies whether an arithmetic/logic shift operation or a normalize operation is to be performed.
The circuit 200 has three primary output values: (a) two 40-bit results aD0 and aD1 written to external accumulator 202 (or other register file), and (b) an overflow flag LMV that is set and written to a status register (not shown). The input value SHIFT applied to multiplexer (mux) 211 selects either 1) the shift value from limiter 210 for an arithmetic shift left or right operation or 2) the shift amount for a normalize operation that is generated by exponent/compare module 205. Barrel shifter 203 performs a shift, either left or right, of the input data aS0 based on the decoded input SV from mux 211. Barrel shifter 203 may include a decoder to translate the value SV from mux 211 into 1) the number of bit positions to shift the input data aS0 and 2) whether to shift the input data aS0 left or right.
The result aD0 is the output of a barrel shift operation applied to the input sequence aS0 by barrel shifter 203, where the sequence length of the result may be limited by saturate module 204. When the overflow flag LMV is not set, the result aD0 may be represented with 32-bits, and so limiting the result from barrel shifter 203 with saturate module 204 is not necessary (SAT is in a xe2x80x9cdon""t carexe2x80x9d state).
When the overflow flag LMV is set, the result aD0 may not be represented with 32 bits (i.e., an overflow occurs). Whether a 32-bit or 40-bit result aD0 is written to the external accumulator is determined by the output signal of AND gate 208 applied to saturate module 204. AND gate 208 generates as an output signal the logical AND of 1) the overflow flag LMV and 2) the saturation mode value SAT. If saturation mode value SAT is enabled, then the output of AND gate 208 causes saturate module 204 to limit the result aD0 to the range 0xff80000000 to 0x007fffffff (Hex). If saturation mode value SAT is disabled, then the output of AND gate 208 causes saturate module 204 to pass the entire 40-bit result aD0 to the external accumulator 202.
For the normalize operation, the BMU 201 shifts the input bits by an appropriate shift amount to represent the value with 32-bits. The shift amount is referred to as the xe2x80x9cexponentxe2x80x9d and the result aD1 is the exponent for the normalize operation. The (e.g., 6-bit) exponent is generated by exponent/compare module 205 based on the input data aS0, and exponent/compare module 205 also generates the logical overflow value LLV component of the overflow flag LMV (described below).
The overflow flag LMV is a value comprising two components. The first component is the logical overflow value LLV determined by exponent/compare module 205. Exponent/compare module 205 compares the 6-bit value SV from the mux 211 to the 6-bit exponent generated for the input data aS0. The exponent also indicates the number of redundant sign bits in the input data aS0. If the shift value is greater than the number of redundant sign bits, a logical overflow has occurred, and exponent/compare module 205 sets the logical overflow value LLV to one. For the described exemplary implementation of the prior art, the logical overflow value LLV is only set to one on left shifts and, by definition, is set to zero on right shifts. The second component of the LMV, sometimes referred to as the math overflow value, is determined after the input has been shifted. A test determines if the bits in the positions corresponding to the guard bits and the most significant bit of the input data aS0, such as bits 39 to 31 in the exemplary embodiment, and the result aD0 are not all the same. Compare module 212 applies the test to the output aD0 prior to application to saturate block 204, and the overflow flag LMV is set when the test determines the bits are not the same. As shown in FIG. 2, the overflow flag LMV is generated by OR gate 209 as a logic OR of 1) the logical overflow value LLV and 2) the math overflow value of the compare module 212. In some implementations, the logical overflow value LLV is a separate flag and the LMV is only set if all of the guard bits are not the same as bit 31.
The present invention relates to faster computation of the overflow flag LMV in a bit manipulation unit (BMU). For fast computation, the overflow flag is computed based on the input data and the shift amount. The overflow flag is calculated separately as either a LMVleft for an arithmetic shift left operation or LMVright, for an arithmetic shift right operation. Calculation of LMVleft and LMVright for an exemplary embodiment may be as follows. For an arithmetic shift left operation, LMVleft may be computed by first adding one plus the number of guard bits in the input data to the shift amount, and then detecting the number of redundant sign bits. Hence, for an arithmetic shift right operation, LMVright, may be computed by combining the total number of redundant sign bits in the input data with the shift amount since a shift right essentially adds more sign bits. By computing the overflow flag separately as LMVleft and LMVright for arithmetic left and right shifts, respectively, the overflow flag LMV is determined in parallel with the barrel shift operation and so does not depend on the result from the barrel shift operation. Since calculation of the overflow flag is part of the critical path of computation in, for example, a BMU, an advantage of the present invention may be a relative reduction in the time necessary for a BMU to calculate the overflow flag.